Adams có trận ra mắt cho đội tuyển Anh trong trận đấu với Tây Ban Nha vào năm 1987, sau đó anh chơi ở Euro 88, ghi được một trong hai bàn thắng của đội tuyển Anh. Anh là cầu thủ đầu tiên trong những cầu thủ được sinh ra sau chiến thắng ở World Cup 1966 có vinh dự khoác áo đội tuyển Anh.

Sau một khởi đầu đầy hứa hẹn trong sự nghiệp ở đội tuyển quốc gia, Adams đã phải chịu một loạt những thất bại trong những năm đầu của thập niên 1990. Anh đã bị loại khỏi đội hình tham dự World Cup 1990 một cách đầy bất ngờ bởi huấn luyện viên Bobby Robson, và đã bỏ lỡ Euro 92 bởi chấn thương. Tuy nhiên, anh vẫn giữ được một vị trí thường xuyên ở hàng phòng ngự, và sau khi Gary Lineker giã từ sân cỏ vào năm 1992, Adams chia sẻ chiếc băng đội trưởng của đội tuyển Anh với David Platt một cách không chính thức, mặc dù vậy Adams đã trở thành đội trưởng đội tuyển Anh ngay trước khi Euro 96 diễn ra, đồng nghĩa với việc vị trí của Platt trở nên khó đảm bảo. Tuyển Anh vào đến bán kết của Euro 96, trước khi để thua trên chấm phạt đền trước tuyển Đức.

Khi huấn luyện viên tuyển Anh Glenn Hoddle lấy chiếc băng đội trưởng từ Adams và trao cho Alan Shearer, đó là viên thuốc đắng mà Adams buộc phải nuốt. Phát biểu tại một diễn đàn của người hâm mộ vào năm 2008 Adams nhấn mạnh "Tôi có một vài sự bất bình trước cái cách mà Glenn Hoddle lấy chiếc băng đội trưởng trao cho Alan Shearer thay vì tôi nhưng tôi có thể bỏ qua điều đó. Tôi đã phản ứng một cách tích cực. Tôi không đồng ý với ông ấy [Hoddle] và ông ấy nghĩ rằng Alan có thể kiếm được nhiều quả phạt đền hơn khi chơi ở vị trí trung phong. Mọi người biết phản ứng của tôi về điều đó".

Adams tiếp tục chơi cho đội tuyển quốc gia, và cuối cùng anh cũng được xuất hiện ở một vòng chung kết World Cup vào năm 1998. Giải đấu quốc tế cuối cùng của anh là màn trình diễn thất vọng của đội tuyển Anh ở chiến dịch Euro 2000. Với việc Shearer giã từ đội tuyển quốc gia sau giải đấu này, Adams đã lấy lại chiếc băng đội trưởng. Tuy nhiên, trong vòng vài tháng, tuyển Anh thất bại ở trận đấu tại vòng loại World Cup trước tuyển Đức vào tháng 10 năm 2000, đó là trận đấu cuối cùng được tổ chức tại Sân vận động Wembley trước khi nó bị phá bỏ để xây dựng lại. Trận đấu đó là lần ra sân thứ 60 của Adams tại Wembley, đó là một kỷ lục. Với việc Sven-Göran Eriksson lên nắm quyền đội tuyển Anh và sự nổi lên của cầu thủ trẻ Rio Ferdinand, Adams giã từ đội tuyển quốc gia trước khi Eriksson chọn lựa đội hình đầu tiên của ông ấy. Anh là tuyển thủ Anh cuối cùng ghi bàn trên Sân vận động Wembley cũ khi anh ghi bàn thắng thứ hai cho đội tuyển Anh trong chiến thắng 2–0 ở trận giao hữu trước Ukraine vào ngày 31 tháng 5 năm 2000. Đây cũng là lần đầu tiên anh ghi bàn kể từ bàn thắng anh ghi được trong trận giao hữu đối đầu với Ả Rập Xê Út vào tháng 11 năm 1988, đây là một kỷ lục cho khoảng thời gian dài nhất giữa hai bàn thắng mà một cầu thủ ghi được cho đội tuyển Anh.

Tổng cộng Adams đã ra sân 66 lần cho đội tuyển Anh, và ghi được 5 bàn thắng.[11]